Section: New Results

Decomposition-based multi-objective optimization

Participants: Dimo Brockhoff, Bilel Derbel, Arnaud Liefooghe, Gauvain Marquet, El-Ghazali Talbi, Saul Zapotecas-Martinez (external collaborators: Hernan Aguirre and Kiyoshi Tanaka, Shinshu Univ., Japan; Juan Palacios Alonso, Univ. Oviedo, Spain)

MOEA/D is an aggregation-based evolutionary algorithm which has been proved extremely efficient and effective for solving multi-objective optimization problems. It is based on the idea of decomposing the original multi-objective problem into several single-objective subproblems by means of well-defined scalarizing functions. Those single-objective subproblems are solved in a cooperative manner by defining a neighborhood relation between them. This makes MOEA/D particularly interesting when attempting to plug and to leverage single-objective optimizers in a multi-objective setting. For continuous optimization, we investigate in [49] the benefits that MOEA/D can achieve when coupled with CMA-ES, which is believed to be a powerful single-objective optimizer. We rely on the ability of CMA-ES to deal with injected solutions in order to update different covariance matrices with respect to each subproblem defined in MOEA/D. We show that by cooperatively evolving neighboring CMA-ES components, we are able to obtain competitive results for different multi-objective benchmark functions. Moreover, in the combinatorial case, we study in [48] the incorporation of geometric differential evolution (gDE), the discrete generalization of DE, into the MOEA/D framework. We conduct preliminary experiments in order to study the effectiveness of gDE when coupled with MOEA/D. Our results indicate that the proposed approach is highly competitive with respect to the original version of MOEA/D, when solving a combinatorial optimization problem having between two and four objective functions. In [36] , we consider a bi-objective scheduling combinatorial problem in which task durations and due-dates are uncertain as a case study for MOEA/D. In particular, we investigate existing variants of MOEA/D and we propose a novel and simple alternative replacement component at the aim of maintaining population diversity. Through extensive experiments, we then provide a comprehensive analysis on the relative performance and the behavior of the considered algorithms. Besides being able to outperform existing MOEA/D variants, as well as the standard NSGA-II algorithm, our investigations provide new insights into the search ability of MOEA/D and highlight new research opportunities for improving its design components. At last, in [32] , we propose the first large-scale message passing distributed scheme for parallelizing the computational flow of MOEA/D. We show how synchronicity and workload granularity can impact both quality and computing time, in an extremely fine-grained configuration. We deploy our distributed protocol using a large-scale environment of 128 computing cores. Besides being able to show significant speed-ups while maintaining competitive search quality, our experimental results provide insights into the behavior of the proposed scheme in terms of quality/speed-up trade-offs; thus pushing a step towards the achievement of effective and efficient parallel decomposition-based approaches for large-scale multi-objective optimization.